/*
 * @lc app=leetcode.cn id=152 lang=java
 *
 * [152] 乘积最大子数组
 */

// @lc code=start
class Solution {
    public int maxProduct(int[] nums) {
        // 动态规划
        // 使用两个数组， 一个是存储最大值的数组，一个是存储最小值的数组

        int len = nums.length;
        int[] f = new int[len+1];
        int[] g = new int[len+1];

        int res = nums[0];

        f[0] = nums[0];
        g[0] = nums[0];

        for(int i = 1; i < len; i++) {
            f[i] = Math.max(nums[i], Math.max(f[i-1]*nums[i], g[i-1]*nums[i]));
            g[i] = Math.min(nums[i], Math.min(f[i-1]*nums[i], g[i-1]*nums[i]));
            res = Math.max(res, f[i]);
        }
        return res;
    }
}
// @lc code=end

